package 力扣.数组.摩尔投票;

public class 多数元素169 {
    public static void main(String[] args) {
        int[] ins = new int[]{2,2,1,1,1,2,2};
//        int[] ins = new int[]{3,1,3};
//        int[] ins = new int[]{10,9,9,9,10};
        int i = majorityElement(ins);
        System.out.println(i);
    }

    /**
     * 摩尔投票：同加异减
     * 前提：结果元素的数量必须大于所有元素的一半
     *
     * 选取数组第一个元素作为`结果元素`，计数`count`初始化为1，遍历数组，遇到**和结果元素相同的元素**则`count++`，
          遇到**和结果元素不同的元素**则`count--`，直到`count == 0`则说明当前元素已经被我们**消耗完了**，该换一个元素了，
          这时使用数组的下一个元素作为**新的结果元素**，`count`重新初始化为`1`，
     * 重复上述操作，直到到达数组末尾。**最后的结果元素即为所求**(因为结果元素的数量大于所有元素的一半，肯定无法被完全消耗)。
     * @param nums
     * @return
     */
    public static int majorityElement(int[] nums) {
        int count = 1;//初始化为1
        int re = nums[0];
        for (int i = 1; i < nums.length; i++) {
            if (count == 0 ){//如果被消耗完毕
                re = nums[i];//选取下一个元素（在这里就是num[i]）作为结果元素，count重新赋值
                count = 1;
                continue;//直接进入下一个
            }
            int te = nums[i];
            if (te == re){//进行结果元素和当前元素的判断
                 count++;
            }else {
                count--;
            }
        }
        return re;//即为结果
    }
}
